@MastersThesis{CoutinhoMosGuiSimReg:1975:AlPrNã,
author = "Coutinho, Artur Aparecido Val{\'e}rio and Mostafe, Mamdouh
Mahmoud and Guimar{\~a}es, Mauro and Simoni, Paulo Ouvera and
Rego, Raimundo de Souza",
title = "Algoritmos de programa{\c{c}}{\~a}o n{\~a}o linear (Volumes I,
II, III, IV, V e VI)",
school = "INPE",
year = "1975",
address = "S{\~a}o Jos{\'e} dos Campos",
month = "1974-06-05",
keywords = "computa{\c{c}}{\~a}o aplicada, algoritmos, algorithms.",
abstract = "VOL. I: Este volume visa fazer uma apresenta{\c{c}}{\~a}o dos
demais volumes, que constituem o corpo do trabalho, bem como as
condi{\c{c}}{\~o}es de utiliza{\c{c}}{\~a}o de cada um dos
algoritmos estudados e programados. Cont{\'e}m ainda uma breve
exposi{\c{c}}{\~a}o de conceitos matem{\'a}ticos,
necess{\'a}rios compreens{\~a}o da parte te6rica dos algoritmos.
ABSTRACT: This volume is comprised of a summary of the complete
work (which follows in five volumes), as well as the conditions
necessary for the application of each of the algorithms studied
and programmed. It also contains some of the mathematical concepts
which are necessary to the understanding of the theory of the
algorithms. VOL II: O objetivo deste trabalho {\'e} apresentar e
discutir em detalhes o M{\'e}todo de Beale para minimizar uma
fun{\c{c}}{\~a}o quadr{\'a}tica, convexa, sujeita a
restri{\c{c}}{\~o}es lineares. {\'E} exigido do leitor
conhecimentos b{\'a}sicos de c{\'a}lculo e de
programa{\c{c}}{\~a}o linear. Inicialmente, com a finalidade de
dar uma conceitua{\c{c}}{\~a}o do algoritmo, apresenta-se um
diagrama de funcionamento do algoritmo e um exemplo simples
resolvido num gr{\'a}fico. Em seguida {\'a} apresentado o
desenvolvimento te{\'o}rico do algoritmo com as necess{\'a}rias
provas matem{\'a}ticas. Tamb{\'e}m {\'e} mostrada a
converg{\^e}ncia do algoritmo. Finalmente, {\'e} apresentada,
uma codifica{\c{c}}{\~a}o em FORTRAN, do algoritmo de Beale para
o computador B-6700 da BURROUGRS. Esta codifica{\c{c}}{\~a}o
{\'e} acompanhada de diagramas e exemplos. ABSTRACT: The
objective of this work is to discuss in detail Beale's method for
minimizing a convex quadratic function, subject to linear
constraints. The reader is supposed to have a background in
calculus and linear programming. At the beginning, with the
purpose of giving a conceptualization of the algorithm, we present
a flow diagram of the algorithm and a simple example solved
graphically. After this, the theoretical development of the
algorithm is presented with the necessary mathematical prooft. The
algorithm convergence is also shown. Finally, a computer programme
of Beale's algorithm is presented, in FORTRAN for the BORROUGHS B
-6700 model. This programe is followed by diagrams and examples.
VOL. III: Este volume apresenta o trabalho relativo aos
m{\'e}todos de Barankin e Dorfman e de Frank e Wolfe. Ambos os
m{\'e}todos minimizam uma fun{\c{c}}{\~a}o quadr{\'a}tica
convexa, cujas vari{\'a}veis s{\~a}o n{\~a}o negativas e
sujeitas a um conjunto de desigualdades lineares. S{\~a}o feitas
transforma{\c{c}}{\~o}es no problema original, baseadas nas
condi{\c{c}}{\~o}es de otimalidade de Kuhn-Tucker, obtendo-se
uma nova fun{\c{c}}{\~a}o a ser minimizada e um conjunto
adicional de restri{\c{c}}{\~o}es. No m{\'e}todo de Barankin e
Dorfman, s{\~a}o utilizadas t{\'e}cnicas modificadas para
programas lineares, a fim de diminuir o valor da nova
fun{\c{c}}{\~a}o objetivo em cada passo. No m{\'e}todo de Frank
e Wolfe, a nova fun{\c{c}}{\~a}o objetivo {\'e} linearizada em
cada passo, sendo minimizada por t{\'e}cnicas de
programa{\c{c}}{\~a}o linear. Os dois m{\'e}todos permitem a
obten{\c{c}}{\~a}o de solu{\c{c}}{\~o}es sub-{\'o}timas para
o problema. Permitem saber, no primeiro passo, se o problema
{\'e} invi{\'a}vel, ilimitado ou se possui solu{\c{c}}{\~a}o
{\'o}tima. Apresentamos a conceitua{\c{c}}{\~a}o do
m{\'e}todo, estudo da teoria e aspectos computacionais, para cada
m{\'e}todo. Acompanha o trabalho a codifica{\c{c}}{\~a}o dos
algoritmos, em FORTRAN para o computador BURROUGES B-6700, e um
roteiro para facilitar a utiliza{\c{c}}{\~a}o destes algoritmos,
contendo a descri{\c{c}}{\~a}o dos par{\^a}metros e a forma de
entrada dos dados. ABSTRACT: This volume presents the work
relative to the methods of Barankin and Dorfman and of Frank and
Wolfe. These methods minimize a convex quadratic function, whose
variables are non-negative and subject to a set of linear
inequalities. Transformations are made on the original problem,
according to Kuhn-Tucker's optimality conditions, resulting in a
new function to be minimized and an additional set of constraints.
In the method of Barankin and Dorfman, modified techniques for
linear programs are used to decrease the value of the new
objective function at each step. In the method of Frank and Wolfe,
the new objective function is linearized at each step and is
minimized by linear programming techniques. Both methods enable us
to get sub-optimal solutions for the problem. It is possible to
know, at the first step, if the problem is infeasible, unlimited
or if it has an optimal solution. We present an intuitive
approach, a theoretical study and computational features for each
method. Computer programmes for the algorithms (in FORTRAN for the
BURROUGHS B-6700 model) and a guide to apply these algorithms,
consisting of a description of the parameters and data input
format, were added to this work. VOL. IV: Este volume apresenta um
trabalho relativo ao m{\'e}todo da Proje{\c{c}}{\~a}o do
Gradiente de Rosen. Este m{\'e}todo maximiza uma
Fun{\c{c}}{\~a}o C{\^o}ncava Diferen{\c{c}}{\'a}vel sujeita a
Restri{\c{c}}{\~o}es Lineares. O M{\'e}todo de Rosen {\'e} um
M{\'e}todo do Gradiente. Sua principal caracter{\'{\i}}stica
{\'e} que durante a maximiza{\c{c}}{\~a}o caminhamos na
dire{\c{c}}{\~a}o da proje{\c{c}}{\~a}o do gradiente sobre o
contorno da regi{\~a}o vi{\'a}vel, sempre que o ponto
perten{\c{c}}a a este contorno e o gradiente aponte para fora.
Este trabalho consta da Teoria e da Conceitua{\c{c}}{\~a}o do
M{\'e}todo, Problemas resolvidos graficamente e uma
discuss{\~a}o das Regras Computacionais Aplicadas. Ele tem
tamb{\'e}m uma Codifica{\c{c}}{\~a}o FORTRAN para o computador
BURROUGHS B-6700 com Instru{\c{c}}{\~o}es para o usu{\'a}rio e
Fluxogramas. ABSTRACT: This volume presents a work about Rosen's
Projection Gradient Method. This Method maximizes a Concave
Differentiable Function subject to Linear Constrainsts Rosen's
Method is a Gradient Method. It is characterized by following the
direction of the gradient projection on the boundary of the
feasible domain, whenever the point belongs to this boundary and
the gradient points outside the feasible domain. This work
contains the Theory and Conceptualization of the Method, Problems
solved graphically, and a discussion on the Computation Rules
applied. It includes a FORTRAN Programme for the BURROUGHS B-6700
computer, Instructions for the user, and Flow Diagrams. VOL. V:
Apresenta-se neste trabalho dois m m{\'e}todos de
minimiza{\c{c}}{\~a}o de fun{\c{c}}{\~o}es de diversas
vari{\'a}veis, sem restri{\c{c}}{\~o}es. M{\'e}todo de
Davidon-Fletcher e Powell. Este m{\'e}todo, baseado nas
id{\'e}ias de Davidon e idealizado por Fletcher e Powell, {\'e}
um dos mais eficientes m{\'e}todos de primeira ordem. As
informa{\c{c}}{\~o}es obtidas nas itera{\c{c}}{\~o}es j{\'a}
executadas s{\~a}o usadas para montar uma matriz que aproxima a
hessiana da fun{\c{c}}{\~a}o sendo minimizada. M{\'e}todo de
Powell. Aplica-se nos casos pr{\'a}ticos onde, normalmente,
derivadas n{\~a}o s{\~a}o de f{\'a}cil c{\'a}lculo. {\'E} uma
simples varia{\c{c}}{\~a}o do m{\'e}todo cl{\'a}ssico de
minimizar uma fun{\c{c}}{\~a}o de diversas vari{\'a}veis
alterando uma s{\'o} vari{\'a}vel por vez. O m{\'e}todo de
Powell {\'e} considerado o mais eficiente dos m{\'e}todos de
minimiza{\c{c}}{\~a}o sem calcular derivadas. Teoremas sobre
converg{\^e}ncia quadr{\'a}tica e estabilidade dos m{\'e}todos
s{\~a}o mostrados. Os dois m{\'e}todos foram programados em
FORTRAN para o computador B-6700. Testes num{\'e}ricos e detalhes
dos programas s{\~a}o inclu{\'{\i}}dos. ABSTRACT: In this work,
two different methods for locating an unconstrained minimum of a
function of several variables are described. - Davidon - Fletcher
and Powell method. This method, based upon the ideas of Davidon
and developed by Fletcher and Powell, is one of the most efficient
first order methods. The information obtained during the
previously made iterations are used in constructing cm
approximation of the hessian of the function being minimized. -
Powell's method. This method is applicable for the practical cases
where, normally, derivatives are not easily calculated. It is a
simple variation of the classical method of minimizing a function
of several variables by changing one parameter at a time. The
method is considered to be the most efficient of all method of
minimization without calculating derivatives. Theorems concerning
the quadratic convergence and stability of the methods are proved.
Computer programmes in FORTRAN for the B-6700 model were prepared
for the two methods. Numerical tests and programme details are
included. VOL. VI: Este trabalho apresenta o Algoritmo dos Pontos
Interiores de Fiacco e McCormick (refer{\^e}ncia {{[6]),}} que
serve para resolver problemas n{\~a}o lineares com
restri{\c{c}}{\~o}es em forma de desigualdades
pass{\'{\i}}veis de serem satisfeitas estritamente. Os mais
importantes resultados matem{\'a}ticos relacionados com o
algoritmo s{\~a}o apresentados em detalhes. Foi desenvolvida uma
codifica{\c{c}}{\~a}o em FORTRAN suficientemente detalhada para
permitir sua utiliza{\c{c}}{\~a}o por pessoas n{\~a}o
especialistas na {\'a}rea. Como se apresenta, esta
codifica{\c{c}}{\~a}o se aplica ao computador BURROUGHS-6700.
Este algoritmo de Fiacco e McCormick se caracteriza como uma
t{\'e}cnica de minimiza{\c{c}}{\~a}o sequencial e irrestrita.
Basicamente o m{\'e}todo agrupa tanto as restri{\c{c}}{\~o}es
quanto a fun{\c{c}}{\~a}o objetivo em uma {\'u}nica
fun{\c{c}}{\~a}o que {\'e} minimizada irrestritamente diversas
vezes, sofrendo entre uma minimiza{\c{c}}{\~a}o e outra uma
pequena altera{\c{c}}{\~a}o em um de seus par{\^a}metros.
ABSTRACT: This work presents the interior points algorithm of
Piacco and McCormick (reference {{[6]),}} which is applicable to
nonlinear programming problems with inequality constraints that
must be satisfiable in the inequality form. The most important
related mathematical results are discussed in details. A FORTRAN
programme, sufficiently detailed to be used by nonspecialists, is
presented. The programme as presented, is to be used in the
BURROUGHS-6700 computer model. The algorithm of Fiacco and
McCormick is characterized as one of the sequential unconstrained
minimization techniques. Basically, the method joins both the
objective function and the constraints in a single function that
is repeatedly minimized with one of its parameters being slightly
changed from one minimization to the other.",
affiliation = "{Instituto Nacional de Pesquisas Espaciais (INPE)} and {Instituto
Nacional de Pesquisas Espaciais (INPE)} and {Instituto Nacional de
Pesquisas Espaciais (INPE)} and {Instituto Nacional de Pesquisas
Espaciais (INPE)} and {Instituto Nacional de Pesquisas Espaciais
(INPE)}",
committee = "Lapa, Jair dos Santos (orientador) and Ferras, Jos{\'e} Eugenio
Guisard and Taube Netto, Miguel",
copyholder = "SID/SCD",
englishtitle = "x",
label = "3517",
language = "pt",
pages = "1176",
targetfile = "INPE-596- v. I a VI.pdf",
urlaccessdate = "01 maio 2024"
}